/**
 * 解题思路: 两指针， 左右相差len-N， 然后， 一起移动， 那么， 第一个到达正数第N个， 后一个指针也就到了倒数第N个了
 */
function Node(val, next){
    // 链表有当前的节点值和下一个节点
    this.val = val === undefined? 0: val
    this.next = next === undefined ? null : next
}

const list = {
    val:1,
    next: {
        val:2,
        next:{
            val:3,
            next:{
                val:4,
                next:null
            }
        }
    }
}

// TODO：复习
// head是链表的头部
function deleteNNode(head, n){
    // 创造一个新的节点指向起点， 那么， 正好在right到达最后一个， left是待删除的前一个(伪节点， 正和我意)
    let dummy = new Node(0, head)
    // left指向第一个节点
    let right = head
    let left = dummy;
    // 将 右边的和左边的之间差设置为N-1个， 这样， 当right为最后节点， left正好是待删除的前一个。 然后让她指向后后一个就可以了
    for(let i=0; i<n-1; i++){
        right = right.next
    }
    while(right){
        // 右边和左边， 各自向后一个移动
        right = right.next;
        left = left.next;
    }
    // 移动到相对应的位置了， 就进行删除操作。
    // 将left的下一个（这个就是待删除）节点， 删除。
    left.next  = left.next.next
    let ans = dummy.next
    // 这里需要删除新建的头节点
    delete dummy
    return ans;
}


/**
 * O(n) 时间复杂度,n为链表的长度，先循环遍历出链表的长度
 */

function delNode(head, n){
    // 先要判断边界条件， 如果是空的， 直接返回
    if(!head) return head
    let len = 0;
    let cur = head
    while(head){
        len++
        head = head.next
    }

    // 这里找到倒数第len - n 个节点， 就是伪节点
    while(i<len - n ){
        cur = cur.next
    }
    cur.next = cur.next.next
    return head;
}

/**
 * 利用栈先进后出的特性，  全部压进去， 然后， 弹出的第n个就是需要删除的
 */

function delNodeByStack(head, n) {
    if(!head) return head
    // 先将所有的节点压进stack中
    let stack = []
    // 新建一个保存首节点
    let dummy = new Node(0, head)
    while(head){
        stack.push(head)
        head = head.next
    }
    // 弹n之前的所有节点
    for(let i=0; i<n; i++){
        stack.pop()
    }
    // 保留倒数第n个节点， 作为头, 如果用了真的stack， 可以直接使用stack.top()
    let prev = stack[stack.length - 1]
    // 删除倒数第n个节点
    prev.next = prev.next.next
    // ans就是本来的首节点
    let ans = dummy.next;
    delete dummy;
    return ans;
}

// 双指针方法
function N(head,n){
    // 新建一个头指针
    let dummy = new Node(0, head)
    let left = head, right = head

    for(let i=0; i < n; i++) {
        right = right.next
    }
    while(right) {
        right = right.next
        left = left.next
    }
    let ans = dummy.next
    left.next = left.next.next
    delete dummy;
    return ans;
}

/**
 * 时间复杂度O(n) 借用栈
 */

function F(nums, n) {
   let stack = [], dummy= new Node(0, head), left = head
    while(left){
       stack.push(left)
        left = left.next
    }
    for(let i =0; i<n; i++){
        stack.pop()
    }
    // 取出最上面的一个
    let cur = stack.shift()
    cur.next = cur.next.next
    let ans = dummy.next
    delete dummy;
    return ans;
}


function Fun(head, n){
    let left , right = head
    let i = 0
    while(i<n){
        i++
        // left = left.next
        right = right.next
    }
    while(right){
        left = left.next
        right = right.next
    }

    let ans = left
    left.next = left.next.next
    delete  left.next
    return ans 
}
